線形秘密分散法:LSSS(Liner Secret Sharing Scheme)
Policy
閾値法では、ある行列のうち、どの行を取り出しても、その逆行列はVandermonde行列の形をしていて逆行列を求めることができた。
例えば、以下の(5,3)閾値法では、どの行を取り出しても逆行列が存在する。
https://scrapbox.io/files/61b2d52f285db20023779df3.png
そして、この性質が3個集まると復号できるという性質を利用して秘密分散している.
この行列少しいじる.$ s,r_0,r_1,r_2 を秘密とし
$ \begin{pmatrix} y_1\\y_2\\y_3\\y_4\\y_5\end{pmatrix}= \begin{pmatrix}0&1&0&0 \\ 1&1&0&0 \\ 0&0&1&0 \\ 0&0&1&1 \\ 1&0&0&1\end{pmatrix}\begin{pmatrix}s\\r_0\\r_1&\\r_2\end{pmatrix}
の関係式で得られる$ y_1,...,y_5を配布する
これを展開すると、
$ (y_1,y_2,y_3,y_4,y_5)=(r_0,s+r_0,r_1,r_1+r_2,s+r_2)
これは
$ r_0,s+r_0=(2,2)閾値法
$ (r_1,r_1+r_2,s+r_2)=(3,3)閾値法
と見ることができる。つまり、$ y_1,y_2の条件もしくは$ y_3,y_4,y_5の条件のいずれかが当てはまれば復元できる
これは論理式に落とし込める問題なので、and/orで秘密分散法を構築することができる。
例えば、s を (A ∧ B) ∨ ((C ∨ D) ∧ E)を満たすように秘密分散すると
最初の条件(A ∧ B)
AとBでsを復元できればよいので、(2,2)閾値法を使う
実際には乱数$ r_1を選んで,Aには$ r_1を,Bには$ r_1+sを渡す
二つ目の条件 ((C ∨ D) ∧ E)
C ∨ DとEに対して(2,2)閾値法を使う
乱数$ r_2を選んで, C ∨ Dには$ r_2を,Eには$ r_2+sを渡す
C ∨ D についてはどちらかがあれば OK なのでそれぞれに $ r_2を渡す
最終的に (A, B, C, D, E) =$ (r_1, r_1 + s, r_2, r_2, r_2 + s) を渡せばよい
実際にこのように配付すると A と B を持っているか，「C または D」かつ E を持っているときに s を復元できる
https://scrapbox.io/files/619e511c7c7be6001f806597.png
上図のように、木構造で表された復号条件をPolicyという。
つまり、どのような鍵を持っていれば復号できるかを決める情報
多項式は関係なさそう
Policyをもとに秘密分散を行う手法を線形秘密分散法と呼び、これにFuzzy IDベース暗号を組み合わせることで属性ベース暗号(ABE:Attribute Based Encryption)が構築される。 CP-ABE（CipherTextPolicy ABE）
暗号文にpolicy、独自の秘密鍵に属性を埋め込む方式
KP-ABE（Key Policy ABE）
暗号文に属性、各自の秘密鍵にpolicyを埋め込む方式
参考文献